Fonctionnement

Le but de cet article n’est pas d’expliquer les automates cellulaires ou leur fonctionnement, mais de montrer un exemple d’implémentation en python. Voici une vidéo qui explique le fonctionnement de l’automate cellulaire single rotation : Les automates cellulaires réversibles - Passe-science #23.

Implémentation

Grille de cellules

Nous allons créer un objet qui représente une grille de cellules. Pour cela, il faut d’abord penser à quelques détails.

Premièrement, la structure de données utilisée pour représenter la grille. Le plus simple en python est d’utiliser une liste de listes de booléens, où True représente une cellule pleine, et False une cellule vide.

Nous allons donc créer l’objet Grid. Cet objet aura pour fonction de représenter des grilles en 2D.

Objet `Grid`

Pour l’initialisation de l’objet Grid, il faut prendre en paramètre la hauteur et la largeur (height et width) souhaitée.

On veut ensuite être sûr que la grille peut être divisée en un voisinage de Margolous, ce qui veut dire que l’on veut une hauteur et une largeur paires.

Enfin, on peut créer cette liste de liste de booléens.

class Grid():
    def __init__(self, width: int, height: int):
        self.width: int = 2 * int(width / 2)
        self.height: int = 2 * int(height / 2)
        self.__grid: bool = [[False for _ in range(self.width)]
                            for _ in range(self.height)]

Ici, j’ai nommé self.__grid l’attribut qui contient la grille. Le fait de faire commencer le nom de l’attribut par __ (deux tirets du bas) fait qu’il devient un attribut privé. Cela signifie qu’il ne sera pas accessible en dehors de l’objet : il est possible d’utiliser self.__grid, mais si vous créez un objet Grid, vous ne pourrez pas lui trouver d’attribut _grid.

J’utilise cela car je veux protéger la modification de cet attribut : je veut que, lorsque l’on essaie de le modifier, il soit possible uniquement de lui donner une valeur qui est une grille correcte (c’est-à-dire une grille de booléens). J’ai donc écrit un accesseur et un mutateur (getter et setter en anglais) :

class Grid():
    ...
    @property
    def grid(self) -> list[list[bool]]:
        """Retourne la grille booléenne"""
        return self.__grid

    @grid.setter
    def grid(self, new_grid: list[list[bool]]) -> None:
        """Vérifier que `new_grid` est correctement typé comme list[list[bool]], et de la bonne taille en fonction de `self.width` et `self.height`."""
        assert len(new_grid) == self.height
        assert all(len(line) == self.width for line in new_grid)
        self.__grid = new_grid

Indexer des cellules dans la grille

Pour manipuler la grille, il est nécessaire d’avoir la possibilité de récupérer le contenu de la grille. Pour cela, on veut pouvoir indexer la grille.

Surchage de l’indexation avec `getitem`

En python, il est possible de définir soi-même ce qui se passe lorsque l’on indexe un objet que l’on a créé.

Dans le cas d’une grille, le code est très simple, puisqu’il suffit d’indexer la liste sous-jacente :

class Grid:
    ...
    def __getitem__(self, idx: int):
        return self.__grid[idx]

Indexation qui gère les dépassements sur les bords

D’un point de vue théorique, les automates cellulaires fonctionnent souvent sur une grille infinie. Il est possible de simuler cela, par exemple en faisant grandir la grille seulement quand cela est nécessaire. Cependant, une solution plus évidente consiste à utiliser une grille finie.

Un des moyens les plus simples de gérer les bords d’une grille finie est de supposer que les bords sont reliés entre eux. Par exemple, dans le jeu Pac Man, lorsque le personnage se déplace jusqu’au bord droit de la grille, il se téléporte au bord gauche, et inversement : les deux bords sont comme “reliés”. Nous allons donc utiliser un principe similaire pour notre automate cellulaire : les bords opposés seront reliés.

Ce choix possède 2 principaux avantages : il évite d’avoir un “bord” dans notre simulation (généralement, cela serait un contour de cellules qui sont toujours mortes quoi qu’il arrive), et surtout il est très simple à programmer : il suffit d’utiliser l’opérateur modulo : %. En effet, l’opérateur modulo permet simplement de faire cela avec des entiers. Si vous prenez un nombre n, faîtes n % 10, et n reviendra à 0 dès que vous dépasserez 10, de la même manière que la position doit revenir à gauche dès que l’on dépasse la droite.

Nous allons donc implémenter la fonction get_item, qui récupère le contenu d’une cellule à une position donnée, mais en prenant en compte note principe de “dépassement” : si la position donnée dépasse un bord, elle sera renvoyée à 0.

class Grid:
    ...
    def get_item(self, y: int, x: int) -> bool:
        grid_at_idx: bool = self.__grid[y % self.height][x % self.width]
        return bool(grid_at_idx)

Affichage

Il faut maintenant penser à l’affichage.

Un petit problème est que les caractères sur un terminal sont généralement 2 fois plus haut que larges. Il vaut donc mieux afficher une cellule avec 2 caractères si on veut éviter d’avoir une image déformée (écrasée horizontalement) de notre grille.

Par exemple, on pourrait utiliser 2 espaces pour une cellule vide, et [] pour une cellule pleine.

Il faut donc bien penser à diviser par 2 la largeur de l’affichage par rapport à la largeur réelle de la fenêtre de terminal.

Pour afficher notre grille, nous allons surcharger la méthode __str__. Cela permet de donner à python une nouvelle façon de transformer notre objet en chaîne de caractères. Il suffira ensuite de faire str(ma_grille) pour avoir une chaîne de caractères qui représente la grille dans son état actuel. Le code est simplement un parcours de la grille qui crée au fur et à mesure la chaîne de caractères :

class Grid:
    ...
    def __str__(self) -> str:
        res = ""
        for line in self.__grid:
            for elt in line:
                res += "[]" if elt else "  "
            res += "\n"
        return res

Voisinage de margolous

Transformer en sous-grille

Il nous faut maintenant coder une méthode qui permettra de manipuler le voisinage de Margolous. Le moyen que j’ai utilisé est de diviser la grille principale en une “grille de grilles” : chaque groupe de 4 cellules du voisinage est mis dans une grille à part, et l’ensemble de tous ces groupes de grilles forme lui-même une grille. C’est assez logique, puisque lorsque l’on visualise ce voisinage, on a tendance à voir une “grande grille”, elle-même subdivisée en plus petits carreaux.

Il faut donc coder une fonction qui permet de transformer notre grille normale en ce que j’ai appelé une subgrid (sous-grille). Voici mon code :

class Grid:
    ...
    def get_subgrid(self):
        # attention : width et height sont les dimensions de subgrid
        # soit la moitié des dimension de self.grid
        width, height = self.width // 2, self.height // 2
        # on initialise une grille vide
        subgrid = [[0 for _ in range(width)] for _ in range(height)]
        # on parcoure les indices de cette grille vide
        for y in range(height):
            for x in range(width):
                # On multiplie par 2 pour revenir à des indices sur grid
                # x et y en minuscules : indices dans subgrid
                # X et Y en majuscules : indices dans grid (du coin supérieur gauche)
                Y = 2 * y
                X = 2 * x
                # on créée une grille 2x2 pour le voisinage de margolous
                cell = Grid(2, 2)
                # on remplis cette grille avec les valeurs de la grille
                cell.grid = [[self.get_item(Y, X),   self.get_item(Y, X+1)],
                             [self.get_item(Y+1, X), self.get_item(Y+1, X+1)]]
                # on met cette cellule de voisinage dans subgrid au bon endroit
                subgrid[y][x] = cell
        return subgrid

Mais l’intérêt du voisinage de Margolous est qu’il se décale une fois sur deux. Il faut donc ajouter un argument à la fonction. Je l’ai appelé shift (décalage en anglais), et les valeurs possibles sont 0 (aucun décalage) ou 1 (décalage d’une cellule vers la droite et vers le bas). Voici la fonction réécrite avec l’argument shift :

class Grid:
    ...
    def get_subgrid(self, shift: int):
        width, height = self.width // 2, self.height // 2
        subgrid = [[0 for _ in range(width)] for _ in range(height)]
        for y in range(height):
            for x in range(width):
                Y = shift + 2 * y
                X = shift + 2 * x
                cell = Grid(2, 2)
                cell.grid = [[self.get_item(Y, X),   self.get_item(Y, X+1)],
                             [self.get_item(Y+1, X), self.get_item(Y+1, X+1)]]
                subgrid[y][x] = cell
        return subgrid

Récupérer depuis une sous-grille

Il faut maintenant faire l’opération inverse : à partir de subgrid, il faut être capable de reconstituer le contenu de la grille normale.

class Grid:
    ...
    def set_from_subgrid(self, subgrid: list[list[Grid]]):
        for y in range(self.height):
            for x in range(self.width):
                self.__grid[y][x] = subgrid[y//2][x//2][y%2][x%2]

Il faut à nouveau faire attention au fait que le voisinage de Margolous se décale une fois sur deux. Lorsque le décalage (shift) est de 1, la sous-grille (subgrid) est décalée par rapport à la grille. Dans ce cas, il faut donc faire le décalage inverse. Cela consiste à déplacer la première colonne de la grille en dernière place, et la première ligne à la fin. Le module numpy possède une fonction roll qui permet justement de faire cette opération. Il faut l’importer (ainsi que la fonction array qui permet de transformer notre grille en objet manipulable par numpy). La méthode roll modifie l’objet afin de faire ce décalage inverse :

from numpy import array as np_array
from numpy import roll as np_roll

class Grid:
    ...
    def roll(self):
        self.__grid = np_array(self.__grid)
        self.__grid = np_roll(self.__grid, 1, axis=0)
        self.__grid = np_roll(self.__grid, 1, axis=1)

Enfin, il faut modifier légèrement la fonction set_from_subgrid afin qu’elle fasse ce décalage lorsque c’est nécessaire, en fonction de la valeur de shift (qui doit donc être passé en argument).

class Grid:
    ...
    def set_from_subgrid(self, subgrid: list[list], shift: int):
        for y in range(self.height):
            for x in range(self.width):
                self.__grid[y][x] = subgrid[y//2][x//2][y%2][x%2]
        if shift == 1:
            self.roll()

Appliquer les règles

Faire tourner une grille de voisins

Il faut maintenant une fonction qui fait tourner une grille de 4 cellules.

Comme il n’y a que 4 valeurs dans chaque cellule de voisinage, il est possible de coder “à la main” cette rotation : on crée une nouvelle grille de 4 valeurs qui est une copie élément par élément de notre cellule de voisinage, mais avec une rotation. Voici le code correspondant :

def rotate_cell(cell: Grid) -> Grid:
    new_cell = Grid(2, 2)
    new_cell.grid = [[cell[0][1], cell[1][1]],
                     [cell[0][0], cell[1][0]]]
    return new_cell

Faire tourner seulement selon les règles

L’automate single rotation n’effectue une rotation que si les cellules sont seules dans leur voisinage. Il faut donc implémenter cette fonction : étant donné un voisinage, s’il contient une seule cellule, le faire tourner, sinon ne rien faire.

def single_rotation(cell: Grid) -> Grid:
    # if there is only one alive cell in the 2x2 neighbourhood
    if sum((cell[0][0], cell[0][1], cell[1][0], cell[1][1])) == 1:
        return rotate_cell(cell)
    return cell

Appliquer les règles sur toute la sous-grille

Il faut simplement créer une nouvelle sous-grille à partir de la grille actuelle, en appliquant single_rotation sur chaque cellule de voisinage.

def single_rotation_on_subgrid(sub: list[list[Grid]]) -> list[list[Grid]]:
    return [[single_rotation(cell) for cell in line]
            for line in sub]

tout faire fonctionner ensemble : `step`

On peut maintenant coder la fonction qui fait avancer la simulation d’une étape : la fonction step. Elle prend en argument le décalage (shift) (j’ai décidé de ne pas le calculer automatiquement pour ne pas donner une responsabilité de plus à mon objet Grid qui contient déjà beaucoup de choses).

class Grid:
    ...
    def step(self, shift: int =0):
        sub = self.get_subgrid(shift=shift)
        sub = single_rotation_on_subgrid(sub)
        self.set_from_subgrid(sub, shift=shift)

Lancer l’exécution

Initialiser une grille

Remplir la grille aléatoirement

On peut vouloir initialiser une grille remplie aléatoirement. Pour cela, on a besoin de la fonction random du module random, et d’une nouvelle méthode dans Grid :

from random import random

class Grid:
    ...
    def randomize_grid(self, proportion: float =.3):
        self.grid = [[random() < proportion for _ in range(self.width)]
                     for _ in range(self.height)]

Il est aussi intéressant de ne pas remplir toute la grille, mais seulement une portion. Par exemple, uniquement un cercle d’un rayon donné :

class Grid:
    ...
    def randomize_grid_circle(self, radius: int, proportion: float =.3):
        """Randomize the grid, but fill only cells that are in a circle of the given radius."""
        self.grid = [[(i**2 + j**2 < radius**2) * (random() < proportion)
                      for i in range(self.width)]
                     for j in range(self.height)]

Faire fonctionner la simulation

Il ne reste que quelques étapes pour faire fonctionner notre automate cellulaire. D’abord, il faut choisir la taille de notre grille. Pour cela, on peut utiliser la fonction get_terminal_size() du module os, qui permet de récupérer la taille de la fenêtre de terminal dans laquelle le programme tourne. Cela va permettre d’adapter la taille de la grille automatiquement à la taille de la fenêtre de terminal.

Il faut donc importer cette fonction :

from os import get_terminal_size

Et ajouter ce code à la fin de notre programme

if __name__ == "__main__":
    # on récupère la taille de la fenêtre de terminal
    width, height = get_terminal_size()
    # il faut diviser la largeur par 2 car chaque cellule prends 2 caractères de largeur
    G = Grid(width//2, height)
    # on remplis aléatoirement une partie de la grille
    G.randomize_grid_circle(radius=10, proportion=.3)
    # boucle d'exécution
    while True:
        # on calcule l'étape suivante puis on affiche
        G.step(0)
        print(G, end="")
        G.step(1)
        print(G, end="")

Meilleur affichage

Si vous exécutez le programme que j’ai décrit pour l’instant, vous remarquerez que l’affichage “saute” : il vacille, comme s’il y avait un câble mal branché sur un vieil écran de télévision.

La raison est assez simple : afficher du texte dans un terminal est plutôt lent, et le fait de remplir l’écran avec du texte prend autant de temps que de calculer l’étape suivante.

Il y a plusieurs solutions à ce problème.

Appuier sur une touche pour aller à l’étape suivante

Une solution très simple consiste à faire en sorte l’utilisateur doive appuyer sur une touche à chaque fois qu’il veut voir l’étape suivante. Cela permet de limiter la vitesse à laquelle les étapes avancent, et donc de limiter les problèmes d’affichage. Pour cela, il suffit d’utiliser la fonction input de python.

if __name__ == "__main__":
    width, height = get_terminal_size()
    G = Grid(width//2, height)
    G.randomize_grid_circle(radius=10, proportion=.3)
    while True:
        G.step(0)
        input(G)
        G.step(1)
        input(G)

Cela élimine la plupart des tressautements, mais ne l’élimine pas complètement.

Utiliser `sys.stdout.write`

La fonction stdout.write du module sys est un peu plus rapide que la fonction print. La fonction stdout.write ne convertit pas automatiquement les objets en chaîne de caractères comme la fonction print. Il faut donc convertir vous-même la grille avec la fonction str.

if __name__ == "__main__":
    from sys import stdout
    width, height = get_terminal_size()
    G = Grid(width//2, height)
    G.randomize_grid_circle(radius=10, proportion=.3)
    while True:
        G.step(0)
        stdout.write(str(G))
        G.step(1)
        stdout.write(str(G))

Ajouter une pause entre chaque étape

Le problème que nous avons maintenant est que l’affichage est trop rapide pour que l’on voie toutes les étapes. Il est préférable d’ajouter une pause pour être sûr que le rafraîchissement soit effectué à chaque fois.

if __name__ == "__main__":
    from sys import stdout
    from time import sleep
    width, height = get_terminal_size()
    G = Grid(width//2, height)
    G.randomize_grid_circle(radius=10, proportion=.3)
    while True:
        G.step(0)
        stdout.write(str(G))
        sleep(0.03)
        G.step(1)
        stdout.write(str(G))
        sleep(0.03)

Il y aura toujours quelques problèmes d’affichage, surtout si vous affichez une grille assez grande, mais l’affichage sera beaucoup plus fluide.

Meilleur caractère pour afficher les cellules pleines

Pour un meilleur rendu visuel, j’utilise le caractère █ (full block). Vous pouvez simplement modifier la fonction __str__ pour mettre le caractère que vous préférez.

Le code complet

from numpy import array as np_array
from numpy import roll as np_roll
from random import random
from os import get_terminal_size



class Grid():
    def __init__(self, width: int, height: int, proportion: float =.3):
        self.width: int = 2 * int(width / 2)
        self.height: int = 2 * int(height / 2)
        # the actual grid of cells
        self.__grid: bool = [[False for _ in range(self.width)]
                       for _ in range(self.height)]
        # set random cells in the grid
        self.randomize_grid(proportion)

    @property
    def grid(self) -> list[list[bool]]:
        return self.__grid

    @grid.setter
    def grid(self, new_grid: list[list[bool]]) -> None:
        # make sure that the given value is correctly typed
        assert len(new_grid) == self.height
        assert all(len(line) == self.width for line in new_grid)
        self.__grid = new_grid

    def randomize_grid(self, proportion: float =.3):
        self.grid = [[random() < proportion for _ in range(self.width)]
                     for _ in range(self.height)]

    def randomize_grid_circle(self, radius: int, proportion: float =.3):
        """Randomize the grid, but fill only cells that are in a circle of the given radius."""
        self.grid = [[(i**2 + j**2 < radius**2) * (random() < proportion)
                      for i in range(self.width)]
                     for j in range(self.height)]

    def __getitem__(self, idx: int):
        return self.__grid[idx]

    def get_item(self, y: int, x: int) -> bool:
        """Index the grid, but avoid index error with a modulo.
        Basically the same as self.__grid[y][x], but makes the grid "wrap around".
        """
        grid_at_idx: bool = self.__grid[y % self.height][x % self.width]
        # make sure to get only True of False
        return bool(grid_at_idx)

    def get_subgrid(self, shift: int):
        """The subgrid is the grid of squares of the margolous neighbourhood.
        It makes it a list[list[list[list[bool]]]] of dimensions
        (width/2) × (height/2) × 2 × 2"""
        width, height = self.width // 2, self.height // 2
        subgrid = [[0 for _ in range(width)] for _ in range(height)]
        for y in range(height):
            for x in range(width):
                Y = shift + 2 * y
                X = shift + 2 * x
                cell = Grid(2, 2)
                cell.grid = [[self.get_item(Y, X),   self.get_item(Y, X+1)],
                             [self.get_item(Y+1, X), self.get_item(Y+1, X+1)]]
                subgrid[y][x] = cell
        return subgrid

    def set_from_subgrid(self, subgrid: list[list], shift: int):
        for y in range(self.height):
            for x in range(self.width):
                self.__grid[y][x] = subgrid[y//2][x//2][y%2][x%2]
        if shift == 1:
            self.roll()

    def roll(self):
        self.__grid = np_array(self.__grid)
        self.__grid = np_roll(self.__grid, 1, axis=0)
        self.__grid = np_roll(self.__grid, 1, axis=1)

    def step(self, shift: int =0):
        sub = self.get_subgrid(shift=shift)
        sub = single_rotation_on_subgrid(sub)
        self.set_from_subgrid(sub, shift=shift)

    def __str__(self) -> str:
        res = ""
        for line in self.__grid:
            for elt in line:
                res += "██" if elt else "  "
            res += "\n"
        return res

def rotate_cell(cell: Grid) -> Grid:
    new_cell = Grid(2, 2)
    new_cell.grid = [[cell[0][1], cell[1][1]],
                     [cell[0][0], cell[1][0]]]
    return new_cell


def single_rotation(cell: Grid) -> Grid:
    # if there is only one alive cell in the 2x2 neighbourhood
    if sum((cell[0][0], cell[0][1], cell[1][0], cell[1][1])) == 1:
        return rotate_cell(cell)
    return cell


def single_rotation_on_subgrid(sub: list[list[Grid]]) -> list[list[Grid]]:
    return [[single_rotation(cell) for cell in line]
            for line in sub]


if __name__ == "__main__":
    from sys import stdout
    from time import sleep
    width, height = get_terminal_size()
    G = Grid(width//2, height)
    G.randomize_grid_circle(radius=10, proportion=.3)
    while True:
        G.step(0)
        stdout.write(str(G))
        sleep(0.03)
        G.step(1)
        stdout.write(str(G))
        sleep(0.03)